
//611.有效三角形的个数
class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        //类似与三数求和，通过固定左右一边，再通过同向双指针找合适的位置
        int n=nums.size(),ret=0;
        sort(nums.begin(),nums.end());
        for(int i=n-1;i>=0;i--)   //固定右边，找[0,i-1]中合适的位置
        {
            int left=0,right=i-1;
            while(left<right)
            {
                if(nums[right]+nums[left]<=nums[i]) left++;
                else         //此时的nums[left],nums[right],nums[i]是满足条件的
                {           //区间[left,right-1]与nums[right],num[i]都可以组成三角型
                    ret+=right-left;  
                    right--;
                }
            }
        }
        return ret;
    }
};